package kyssion.leetcode.num51_100;


public class code85_返回最大矩形的面积 {

    public static void main(String[] args) {
        System.out.println(new code85_返回最大矩形的面积().maximalRectangle(
                new char[][]{
                }
        ));
    }

    public int maximalRectangle(char[][] matrix) {
        if (matrix.length==0||matrix[0].length==0){
            return 0;
        }
        int[][] dp = new int[matrix.length][matrix[0].length];
        for (int a = 0; a < matrix[0].length; a++) {
            for (int b = 0; b < matrix.length; b++) {
                if (matrix[b][a] == '1') {
                    dp[b][a] = b == 0 ? 1 : dp[b-1][a] + 1;
                }
            }
        }
        int[] stack = new int[matrix.length];
        int max = 0;
        for (int a = 0; a < matrix.length; a++) {
            max = Math.max(max,largestRectangleArea2(dp[a]));
        }
        return max;
    }
    public int largestRectangleArea2(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        return getMax(heights, 0, heights.length);
    }

    int getMax(int[] heights, int s, int e) {
        if (s >= e) return heights[s];
        int min = s;
        boolean sorted = true;
        for (int i = s; i < e; i++) {
            if (i > s && heights[i] < heights[i - 1]) sorted = false;
            if (heights[min] > heights[i]) min = i;
        }
        //这里可能优化了性能
        if (sorted) {
            int max = 0;
            for (int i = s; i < e; i++) {
                max = Math.max(max, heights[i] * (e - i));
            }
            return max;
        }
        int left = (min > s) ? getMax(heights, s, min) : 0;
        int right = (min < e - 1) ? getMax(heights, min + 1, e) : 0;
        return Math.max(Math.max(left, right), (e - s) * heights[min]);
    }



    public int maximalRectangle2(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return 0;
        int m = matrix.length;
        int n = matrix[0].length;
        int maxArea = 0;
        int[] left = new int[n];
        int[] right = new int[n];
        int[] height = new int[n];
        //初始化
        for (int i = 0; i < n; ++i) {
            left[i] = 0;
            right[i] = n;
            height[i] = 0;
        }
        //计算高度
        for (int i = 0; i < m; ++i) {
            int cur_left = 0, cur_right = n;
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == '1')
                    height[j]++;
                else
                    height[j] = 0;
            }
            //计算左边界，从左到右
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == '1')
                    left[j] = Math.max(left[j], cur_left);
                else {
                    left[j] = 0;
                    cur_left = j + 1;
                }
            }
            //计算右边界，从右到左
            for (int j = n - 1; j >= 0; --j) {
                if (matrix[i][j] == '1')
                    right[j] = Math.min(right[j], cur_right);
                else {
                    right[j] = n;
                    cur_right = j;
                }
            }
            //计算最大面积
            for (int j = 0; j < n; ++j)
                maxArea = Math.max(maxArea, (right[j] - left[j]) * height[j]);
        }
        return maxArea;
    }
}
